import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

// 力扣289. 生命游戏
class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;

        // 方向数组，用于遍历周围的8个方向
        int[][] dirs = {
                {-1, -1}, {-1, 0}, {-1, 1},
                {0, -1},         {0, 1},
                {1, -1},  {1, 0}, {1, 1}
        };

        // 第一遍遍历：标记需要更新的细胞
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;

                // 统计周围活细胞的数量
                for (int[] dir : dirs) {
                    int x = i + dir[0];
                    int y = j + dir[1];

                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        // 注意：标记为2的细胞原本是活的
                        if (board[x][y] == 1||board[x][y]==2) {
                            liveNeighbors++;
                        }
                    }
                }

                // 应用生命游戏的规则
                // 换一个方式来存活细胞和死细胞,这样就不会影响到我们统计 八个相邻位置 的活细胞数了
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 2; // 1 -> 0，标记为2
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = -1; // 0 -> 1，标记为-1
                    }
                }
            }
        }

        // 第二遍遍历：将标记转换为最终的0或1 (最后更新一下即可)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                } else if (board[i][j] == -1) {
                    board[i][j] = 1;
                }
            }
        }
    }
}


// 力扣383. 赎金信
class Solution1 {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hash = new int[26];
        for(int i=0;i<magazine.length();i++){
            char c = magazine.charAt(i);
            hash[c-'a']++;
        }

        int[] hash1 = new int[26];
        for(int i=0;i<ransomNote.length();i++){
            char c = ransomNote.charAt(i);
            if(hash[c-'a']==0 || hash[c-'a']<=hash1[c-'a']){
                return false;
            }
            if(hash[c-'a']>hash1[c-'a']){
                hash1[c-'a']++;
            }
        }
        return true;
    }
}


// 力扣205. 同构字符串
class Solution2 {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] maps = new int[128]; // 存储 s 到 t 的映射
        int[] mapt = new int[128]; // 存储 t 到 s 的映射
        Arrays.fill(maps, -1);
        Arrays.fill(mapt, -1);

        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);

            // 如果 s[i] 还没有映射
            if (maps[sc] == -1) {
                // 但 t[i] 已经有映射了，说明冲突
                if (mapt[tc] != -1) {
                    return false;
                }
                // 建立双向映射
                maps[sc] = tc;
                mapt[tc] = sc;
            }
            // 如果 s[i] 已有映射，但与 t[i] 不匹配
            else if (maps[sc] != tc) {
                return false;
            }
        }
        return true;
    }
}
